
#include <iostream>
#include <fstream>
#include "sqlist.h"

using namespace std;

typedef int elemtype;
typedef sqlisttpl<elemtype> sqlist;

sqlist intersection( sqlist &, sqlist & );
sqlist intersection2( sqlist &, sqlist & );

int main()
{
    ifstream in( "in.txt" );
    vector<elemtype> va, vb;
    sqlist sa, sb, sc;
    int i, n;
    int t;

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	va.push_back(t);
    }

    in >> n;
    for ( i = 0; i < n; i++ ){
	in >> t;
	vb.push_back(t);
    }

    sa.create( va );
    sa.print(); cout << endl;
    sb.create( vb );
    sb.print(); cout << endl;

    sc = intersection2( sa, sb );
    sc.print(); cout << endl;

    return 0;
}

/* ******************************************************
 *             Answer to this question.
 * ******************************************************/

sqlist intersection( sqlist &a, sqlist &b )
{
    sqlist c;
    int i, j, k;
    int sa = a.length(), sb = b.length();
    
    i = j = k = 0;
    while( i < sa && j < sb ){
        while( i < sb && b[j] < a[i] ) j++;
        if( j < sb && b[j] == a[i] ){
            c.inc(1);
            c[k++] = a[i];
        }
        i++;
    }
    
    return c;
}

sqlist intersection2( sqlist &a, sqlist &b )
{
    sqlist c;
    int i, j, k, sa, sb;
    
    sa = a.length();
    sb = b.length();
    i = j = k = 0;
    while( i<sa && j<sb ){
	
	if( a[i] < b[j] ) i++;
	else if( a[i] > b[j] ) j++;
	else{
	    c.inc(1);
	    c[k++] = a[i];
	    i++, j++;
	}
    }
	
    return c;
}
